/*
https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/565551054/

24/9/15
二分搜索
*/


        class Solution {
public:
    // 辅助函数，检查在给定的最小距离 `minDist` 下，是否可以放置至少 `m` 个球
    bool canPlaceBalls(vector<int>& positions, int minDist, int m) {
        int lastPosition = positions[0]; // 上一个放置球的位置
        m--; // 放置第一个球

        int i = 1;
        while (i < positions.size()) {
            // 如果当前位置与上一个放置球的位置之间的距离大于等于 `minDist`
            if (positions[i] - lastPosition >= minDist) {
                m--; // 放置一个球
                lastPosition = positions[i]; // 更新上一个放置球的位置
            }
            i++;
        }
        // 如果所有球都已放置成功，返回 true
        return m <= 0;
    }

    // 主函数，计算可以放置 `m` 个球的最大最小距离
    int maxDistance(vector<int>& positions, int m) {
        sort(positions.begin(), positions.end()); // 对位置数组进行排序

        int n = positions.size(); // 获取位置数组的大小
        int left = 1; // 二分查找的左边界，最小可能的距离
        int right = positions[n - 1] - positions[0]; // 二分查找的右边界，最大可能的距离

        // 使用二分查找来确定最大最小距离
        while (left < right) {
            int mid = left + (right - left + 1) / 2; // 计算中间值
            if (canPlaceBalls(positions, mid, m)) {
                left = mid; // 如果可以放置所有球，尝试更大的距离
            } else {
                right = mid - 1; // 否则，尝试更小的距离
            }
        }

        return left; // 返回最大最小距离
    }
};

